package astar;

import java.util.ArrayList;
import java.util.List;


public class AStar {
	
    public List<Node> exploredNodes;
    public Node closestNode;
    
    private DistanceCalculator distanceCalculator;

    public AStar() {
    	this.distanceCalculator = new DistanceCalculator();
    	this.exploredNodes = new ArrayList<Node>();
    }
    
    public Path getPath(int startX, int startY, int destinationX, int destinationY, Area area, int somewhatPassableCostMultiplicator) {
        long st = System.currentTimeMillis();
        
        reinit();
        
    	if(startX == destinationX && startY == destinationY) {
    		Node[] nodes = new Node[1];
    		List<Node> exploredNodes = new ArrayList<Node>(1);
    		exploredNodes.add(new Node(startX, startY));
    		this.exploredNodes = exploredNodes;
    		return new Path(nodes, true, System.currentTimeMillis()-st, exploredNodes);
    	}

    	NodeList openList = new NodeList(area.width, area.height);
    	NodeList closedList = new NodeList(area.width, area.height);

    	Node n1 = new Node(destinationX, destinationY);
    	Node n2 = new Node(startX, startY);

    	double g = this.distanceCalculator.getDistance(n1, n2);
    	Node finish = new Node(destinationX,destinationY);
    	finish.g = g;

    	Node startNode = new Node(startX, startY);
    	startNode.g = 0;
    	startNode.h = this.distanceCalculator.getDistance(n2, finish);

    	openList.add(startNode);

    	Node currentNode = null;

    	int somewhatPassableGAddendum = AStarConstants.UNIT_SIZE * somewhatPassableCostMultiplicator;

    	boolean arrivedAtDestination = false;
    	while(openList.size != 0) {
    		currentNode = openList.getLowestFNode();
    		if(finish.equals(currentNode)) {
    			arrivedAtDestination = true;
    			break;
    		}

    		openList.remove(currentNode.x, currentNode.y);
    		closedList.add(currentNode);

    		this.processSucessors(currentNode, openList, closedList,finish,area,somewhatPassableGAddendum);
    	}

    	Node endNode = null;
    	if(arrivedAtDestination) {
    		endNode = currentNode;
    	} else {
    		endNode = this.closestNode;
    	}

    	int pathNodesCount = endNode.getParentsCount()+1;
    	Node[] pathNodes = new Node[pathNodesCount];
    	Node tempNode = endNode;
    	int i = 0;
    	float euclidianLength = 0;
    	while(tempNode!=null) {
    		int pos = pathNodesCount-1-i;
    		pathNodes[pos] = tempNode;
    		euclidianLength += tempNode.g;
    		i = i+1;
    		tempNode = tempNode.getParent();
    	}
    	Path path = new Path(pathNodes, arrivedAtDestination, System.currentTimeMillis()-st, this.exploredNodes);

    	return path;
    }
    
    private void processSucessors(Node currentNode, NodeList openList, NodeList closedList, Node finish, Area area, int somewhatPassableGAddendum) {
    	//Get all neighbors of analyzed node, that DO NOT contain impassable terrain:
        Node[] neighbors = this.distanceCalculator.getNeighbors(currentNode, area);

    	for(int i = 0; i<neighbors.length; i++) {
    		Node neighbor = neighbors[i];
    		
    		//if neighbor node is already IN THE CLOSED LIST, skip it:
            Node closedNode = closedList.searchByPosition(neighbor.x, neighbor.y);
            if (closedNode != null) {
                continue;
            }
    		
    		//calculate the cost of getting to the neighbor THROUGH the currently analyzed node:
    		double newG = currentNode.g + this.distanceCalculator.getDistance(currentNode, neighbor);

    		//if this neighbor node contains somewhat passable terrain, add some extra value to it's g cost:
    		//TODO: this should be made up so that each node can have a specific value for it's extra g cost 
    		//(and not simply a constant which applies to all somewhat passable terrain nodes):
    		if(area.getTerrainAt(neighbor.x, neighbor.y) == AStarConstants.TERRAIN_SOME_WHAT_PASSABLE) {
    			newG = newG+somewhatPassableGAddendum;
    		}

    		//if the neighbor is alerady IN THE OPEN LIST *AND* IT'S THERE WITH A LOWER G COST, skip it
    		//as this means that this neighbor is already present in some other path (has some other parent) which is better than
    		//what we're investigating rigth now:
    		Node openNode = openList.searchByPosition(neighbor.x, neighbor.y);
    		if (openNode != null && openNode.g <= newG) {
    			continue;
    		}

    		//if we're here, that means that this neighbor represents a node worth investigating as a potential member of the best path
    		
    		//if this neighbor is present in the open list, but with a worse (higher) g score, then remove it from the opened list
    		//this means that this neighbor has made it to the open list already, but with a parent which constitutes for a path which is
    		//longer (costlier) than if it were to go through the currently analysed node (have it as parent)
    		if (openNode != null /* implicit: && openNode.g <= newG */) {
    			openList.remove(neighbor.x, neighbor.y);
    		} else {
    		    this.exploredNodes.add(neighbor);
    		}

    		/* 
    		 * at this point we know that this neighbor is:
    		 * - not on the closed list
    		 * - is walkable (does not contain impassable terrain)
    		 * - either
    		 *    - not on the open list
    		 *    - on the open list, but with a g cost higher than if it were to pass through the currently analysed node 
    		 *    (aka: if we replace it's current parent with the currently analyzed node, it will make for a less costly (shorter) path
    		 * 
    		 * Set it's g and h scores, set the currently analyzed node as its parent, and add it to the opened list:    		 * 
    		 */    		
    		neighbor.g = newG;
    		neighbor.h = this.distanceCalculator.getDistance(neighbor,finish);
    		neighbor.setParent(currentNode);
    		if(this.closestNode == null || (neighbor!=null && this.closestNode.h > neighbor.h)) {
    			this.closestNode = neighbor;
    		}
    		openList.add(neighbor);
    	}
    }
    
    private void reinit() {
        this.exploredNodes = new ArrayList<Node>();
        this.closestNode = null;
    }

}
